package com.zhupf.dynamic;

/**
 * @author zhupf
 * @date 2024年04月25日 17:11
 * @Description
 *
 *  32. 最长有效括号
 *
 *  给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
 * 子串
 * 的长度。
 *
 * 示例 1：
 *
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 示例 2：
 *
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 示例 3：
 *
 * 输入：s = ""
 * 输出：0
 */
public class LongestValidParentheses {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()(())"));
    }

    public static int longestValidParentheses(String s) {
        s = ")" + s;
        int len = s.length();
        char[] chars = s.toCharArray();
        int[] dp = new int[len];
        int max = 0;
        for (int i = 2; i < len; i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = dp[i - 2] + 2;
                } else {
                    if (chars[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - dp[i - 1] - 2]+dp[i - 1]+2;
                    }
                }
                max = Math.max(dp[i], max);
            }
        }

        return max;
    }


}
